package com.freedy.dataStructure.tree;

import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.StringJoiner;

/**
 * 实现线索化的二叉树
 * @author Freedy
 * @date 2021/3/24 10:47
 */
public class ThreadedBinaryTree<T> {
    private final Node<T> root;
    //为了实现线索化，需要创建要给指向当前节点的前驱节点的指针
    private Node<T> preNode;
    private Node<T> temp;
    private Node<T> last;

    public void threadedNodes(){
        threadedNodes(root);
    }

    public void threadedNodes(Node<T> node){
        if (node==null) return;
        //先线索话左子树
        threadedNodes(node.getLeftNode());
        //先线索话当前节点
        if (node.getLeftNode()==null){
            //就让点前节点的做指针指向前驱节点
            node.setLeftNode(preNode);
            node.setLeftType(1);
        }else{
            node.setLeftType(0);
        }
        if (preNode!=null&&preNode.getRightNode()==null){
            //就让点前节点的做指针指向前驱节点
            preNode.setRightNode(node);
            preNode.setRightType(1);
        }else if (preNode!=null){
            preNode.setRightType(0);
        }
        preNode=node;
        //先线索话右子树
        threadedNodes(node.getRightNode());
    }

    public ThreadedBinaryTree(T data) {
        root = new Node<>();
        root.setData(data);
        temp = root;
        last = root;
    }

    public ThreadedBinaryTree(Node<T> root) {
        this.root = root;
        temp = root;
        last = root;
    }

    /**
     * 向左插入，并且下一次操作是以你现在插入的那个为准
     */
    public ThreadedBinaryTree<T> putLeft(T data) {
        last = temp;
        Node<T> node = new Node<>();
        node.setData(data);
        temp.setLeftNode(node);
        temp = node;
        return this;
    }

    /**
     * 向有插入，并且下一次操作是以你现在插入的那个为准
     */
    public ThreadedBinaryTree<T> putRight(T data) {
        last = temp;
        Node<T> node = new Node<>();
        node.setData(data);
        temp.setRightNode(node);
        temp = node;
        return this;
    }

    /**
     * 让插入标准 回到root
     */
    public ThreadedBinaryTree<T> returnRoot() {
        temp = root;
        return this;
    }

    /**
     * 让插入标准 回到上次操作
     */
    public ThreadedBinaryTree<T> returnLast() {
        temp = last;
        return this;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        if (root != null) root.preOrder();
    }

    /**
     * 中续遍历
     */
    public void infixOrder() {
        if (root != null) root.infixOrder();
    }

    /**
     * 中序遍历节点全部信息
     */
    public void infixOrderNode(){
        ArrayList<Node<T>> list = new ArrayList<>();
        root.infixOrderNode(list);
        for (Node<T> tNode : list) {
            System.out.println(tNode);
        }
    }

    /**
     * 后续遍历
     */
    public void postOrder() {
        if (root != null) root.postOrder();
    }

    /**
     * 判断树是否包含某个节点
     */
    public Node<T> search(T data) {
        return root.search(data);
    }

    /**
     * 删除树上的某个节点,并且连同该节点的子树
     */
    public Boolean del(T data) {
        if (root.data.equals(data)) return true;
        return root.deleteNode(data);
    }

    public static class Node<T> {
        private T data;
        private Node<T> leftNode;
        private Node<T> rightNode;
        private int leftType;//0代表指向左子树，1表示前驱节点
        private int rightType;//0代表指向右子树，1表示后继节点

        public int getLeftType() {
            return leftType;
        }

        public void setLeftType(int leftType) {
            this.leftType = leftType;
        }

        public int getRightType() {
            return rightType;
        }

        public void setRightType(int rightType) {
            this.rightType = rightType;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node<T> getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node<T> leftNode) {
            this.leftNode = leftNode;
        }

        public Node<T> getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node<T> rightNode) {
            this.rightNode = rightNode;
        }

        @Override
        public String toString() {
            String s = super.toString();
            return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
                    .add("id=" + hashCode())
                    .add("data=" + data)
                    .add("leftType=" + leftType)
                    .add("rightType=" + rightType)
                    .add("leftNode=" + (leftNode==null?null :leftNode.hashCode()+""))
                    .add("rightNode=" + (rightNode==null?null :rightNode.hashCode()+""))
                    .toString();
        }

        /**
         * 前中后序遍历
         */
        public void preOrder() {
            System.out.println(this);
            if (leftNode != null&&leftType!=1) {
                leftNode.preOrder();
            }
            if (rightNode != null&&rightType!=1) {
                rightNode.preOrder();
            }
        }

        public void infixOrder() {
            if (leftNode != null&&leftType!=1) {
                leftNode.infixOrder();
            }
            System.out.println(this);
            if (rightNode != null&&rightType!=1) {
                rightNode.infixOrder();
            }
        }

        public void infixOrderNode(ArrayList<Node<T>> list) {
            if (leftNode != null&&leftType!=1) {
                leftNode.infixOrderNode(list);
            }
            list.add(this);
            if (rightNode != null&&rightType!=1) {
                rightNode.infixOrderNode(list);
            }
        }

        public void postOrder() {
            if (leftNode != null&&leftType!=1) {
                leftNode.postOrder();
            }
            if (rightNode != null&&rightType!=1) {
                rightNode.postOrder();
            }
            System.out.println(this);
        }

        public Node<T> search(T data){
            if (this.data.equals(data)) return this;
            Node<T> node = null;
            if (leftNode != null&&leftType!=1) {
                node = leftNode.search(data);
                if (node!=null) return node;
            }
            if (rightNode != null&&rightType!=1) {
                node=rightNode.search(data);
            }
            return node;
        }

        public Boolean deleteNode(T data) {
            if (leftNode!=null&&leftNode.getData().equals(data)){
                leftNode=null;
                return true;
            }
            if (rightNode != null&&rightNode.getData().equals(data)) {
                rightNode=null;
                return true;
            }
            if (leftNode != null) {
                boolean left = leftNode.deleteNode(data);
                if (left) return true;
            }
            if (rightNode != null) {
                return rightNode.deleteNode(data);
            }
            return false;
        }

    }
}
